33. Любимые числа Деда Мороза

Дед Мороз любил развлекаться с числами и цифрами. Более всего он любил цифру 1, ведь именно 1.01 начинается Новый Год.

Шли годы, но он так и остался суеверным – он не любил чисел, у которых после 1 стоит 3, то есть образуется число 13. На Новый Год он решил дать новое задание: посчитать, сколько любимых Дедом Морозом простых чисел есть на промежутке [a, b]?

Вход. Единственная строка, содержащая два числа: начало a и конец b заданного промежутка (1 ≤ a ≤ b ≤ 500000).

Выход. Количество любимых Дедом Морозом простых чисел.

Пример входа	Пример выхода
9 23	4

РЕШЕНИЕ

решето Эратосфена

Анализ алгоритма

Запустим решето Эратосфена, установив простоту натуральных чисел до 500000. Для каждого запроса следует просмотреть все числа от a до b и подсчитать сколько из них являются простыми и не содержат в десятичной записи 13.

Пример

На промежутке [9; 23] имеются 4 простых числа, не содержащие в десятичной записи 13. Это числа 11, 17, 19, 23.

Реализация алгоритма

Объявим глобальный массив для установки простоты чисел.

#define MAX 500100

int primes[MAX];

Функция gen_primes строит массив primes для тестирования чисел на простоту.

void gen_primes(void)

{

int i, j;

for(i = 0; i < MAX; i++) primes[i] = 1;

primes[0] = primes[1] = 0;

for(i = 2; i < sqrt(MAX); i++)

if (primes[i])

for(j = i * i; j < MAX; j += i) primes[j] = 0;

}

Функция Has13 возвращает 1, если число n в своей записи содержит 13.

int Has13(int n)

{

while(n > 0)

{

if (n % 100 == 13) return 1;

n /= 10;

}

return 0;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&n,&m);

Запускаем решето Эратосфена.

gen_primes();

Перебираем числа от n до m. Подсчитываем сколько из них являются простыми и не содержат в десятичной записи 13.

res = 0;

for(i = n; i <= m; i++)

if (primes[i] && !Has13(i)) res++;

Выводим ответ.

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

final static int MAX = 500100;

static boolean[] primes = new boolean[MAX];

public static void gen_primes()

{

int i, j;

Arrays.fill(primes, true);

primes[0] = primes[1] = false;

for(i = 2; i <= Math.sqrt(1.0*MAX); i++)

if (primes[i])

for(j = i * i; j < MAX; j += i) primes[j] = false;

}

public static boolean Has13(int n)

{

while(n > 0)

{

if (n % 100 == 13) return true;

n /= 10;

}

return false;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int a = con.nextInt();

int b = con.nextInt();

gen_primes();

int res = 0;

for(int i = a; i <= b; i++)

if (primes[i] && !Has13(i)) res++;

System.out.println(res);

con.close();

}

}